package TP4.ejercicio3;

import TP2.sorters.AbstractSorter;
import anaydis.sort.SorterType;

import java.util.Comparator;
import java.util.List;

/**
 * Created by IntelliJ IDEA.
 * User: pc
 * Date: 25/10/11
 * Time: 20:56
 * To change this template use File | Settings | File Templates.
 */
public class MergeSorter extends AbstractSorter{

    int implementation; //impl = 0: Top-Down
                        //impl != 0: Bottom-Up

    public MergeSorter(){
        this(SorterType.MERGE);
        implementation = 0;
    }

    public MergeSorter(final SorterType type){
        super(type);
    }

    public <T> void sort(Comparator<T> comparator, List<T> list){
        if(implementation == 0) topDownSort(comparator, list, 0, list.size());
        else bottomUpSort(comparator, list, 0, list.size());
    }

    public <T> void topDownSort(Comparator<T> comparator, List<T> list, int min, int max){
        int m = min + (max-min)/2;
        topDownSort(comparator, list, min, m);
        topDownSort(comparator, list, m+1, max);
        inPlaceMerge(comparator, list, min, m, m+1, max);
    }

    public <T> void bottomUpSort(Comparator<T> comparator, List<T> list, int min, int max){
        for(int i = 1; i < max; i = 2*i){
            for(int j = 0; j < max-i; j += 2*i){
                inPlaceMerge(comparator, list, j, j+i, j+i+1, Math.min(i+2*max, max));
            }
        }
    }

    public <T> void inPlaceMerge(Comparator<T> comparator, List<T> list, int amin, int amax, int bmin, int bmax){
        int i = amin;
        int j = bmin;

        while((i <= amax) || (j <= bmax)){
            if(greater(comparator, list, i, j)){
                swap(list, i, j);
                i++;
            }
            else j++;
        }
    }
}
